package graph_viewer.structure;

import java.awt.Graphics;
import javax.swing.*;
import java.util.*;

import graph_viewer.canvas.*;

import graph_viewer.util.*;

public abstract class Basic_Graph implements Graph{	
	public void do_pre_clustering_animation( int thresholding, Graph_Canvas graph_canvas ){}
	public void do_post_clustering_animation( int thresholding, Graph_Canvas graph_canvas ){}
	
	public void update_related_cluster_edges( Node a_node, Node replaced_node ){}//implementaion only in Clustered_Graph
	public void delete_related_cluster_edges( Node a_node ){}

	public ArrayList find_psuedo_clusters( Collection a_tree_node_collection ){
		ArrayList psuedo_clusters = new ArrayList();

		for (Iterator _i = a_tree_node_collection.iterator(); _i.hasNext(); ){
			Node node	= (Node)_i.next();

			if ( node.get_is_psuedo() ){
				psuedo_clusters.add( node );
			}
		}

		return psuedo_clusters;
	}
	
	public ArrayList	find_leaf_clusters( ){
		ArrayList a_tree_node_collection = find_nodes();

		ArrayList leaf_clusters = new ArrayList();

		for (Iterator _i = a_tree_node_collection.iterator(); _i.hasNext(); ){
			Node node	= (Node)_i.next();
			Debug.println( node + " is leaf cluster? ", 21 );
			if ( node.is_leaf_cluster() ){
				leaf_clusters.add( node );
				Debug.println( "\tyeh", 21 );
			}else{
				Debug.println( "\tno", 21 );
			}
		}

		return leaf_clusters;
	}

	//@return the edges under the cluster
	public ArrayList	find_internal_cluster_edges( Node cluster ){			
		ArrayList	 cluster_edges	= new ArrayList();

		if ( cluster.is_leaf() ){
			return cluster_edges;
		}

		Tree	tree	= find_tree();
		ArrayList	 children	 = cluster.get_children();

		ArrayList edges			=	find_edges();
		for ( Iterator _i = edges.iterator() ; _i.hasNext(); ){
			String[] e = (String[])_i.next();
			
			String
				cluster_label		= cluster.get_label(),
				start_node_label	= e[0],
				end_node_label	= e[1];

			Node
				start_node	= search( start_node_label ),
				end_node	=search( end_node_label );
			
			boolean 
				is_start_node_under_this_cluster		= false,
				is_end_node_under_this_cluster		= false;


			String
				start_cluster_label="+", end_cluster_label="-";

			/*if ( cluster.is_root() ){
				Debug.println( "Test edge: " + start_node_label + "=" + end_node_label, 3 );
			}*/

			for ( Iterator _j = children.iterator() ; _j.hasNext(); ){
				Node		child			= (Node)_j.next();
				String		child_label	= child.get_label();
				//at start_node branch
				if ( tree.is_ancestor( child, start_node ) || child_label.equals( start_node_label )  ){
					is_start_node_under_this_cluster = true;
					start_cluster_label = child_label;
				}
				//at end_node_branch
				if ( tree.is_ancestor( child, end_node ) || child_label.equals( end_node_label )  ){
					is_end_node_under_this_cluster = true;
					end_cluster_label = child_label;
				}

				/*
				if ( cluster.is_root() ){
					Debug.println( "	start_node_label is:" + start_node_label, 3 );
					Debug.println( "	end_node_label is:" + end_node_label, 3 );

					Debug.println( "	child is: " + child_label + "is_start_node_under_this_cluster? " + is_start_node_under_this_cluster + ", is_end_node_under_this_cluster? " + is_end_node_under_this_cluster, 3 );
				}*/

			}

			if ( is_start_node_under_this_cluster && is_end_node_under_this_cluster ){
				//Debug.println( "	both nodes under_this_cluster" , 3 );
				if (! start_cluster_label.equals( end_cluster_label ) ){
					//Debug.println( "	Find a cluster edge: " + start_cluster_label + "&" + end_cluster_label, 3 );
					Edge cluster_edge	= new Edge(search( start_cluster_label ), search( end_cluster_label ) );
					
					cluster_edges.add( cluster_edge  );
				}
			}
			/*
			if ( cluster.is_root() ){
				Debug.println( "End of Test edge: " + start_node_label + "=" + end_node_label, 3 );
			}*/
		}

		return cluster_edges;
	}
	
	public ArrayList find_displayed_nodes(){
		ArrayList displayed_nodes	= new ArrayList();

		for ( Iterator _i = find_nodes().iterator(); _i.hasNext(); ){
			Node a_node = (Node)_i.next();

			if ( a_node.is_displayed() ){
				displayed_nodes.add( a_node );
			}
		}

		return displayed_nodes;
	}

	//@return true if a_node is under a_cluster. 
	private boolean is_under_cluster( Node a_node, Node a_cluster ){
		Tree	tree	= find_tree();

		boolean 
			is_the_cluster = a_node.get_label().equals( a_cluster.get_label() ),
			is_the_cluster_desc	= tree.is_ancestor( a_cluster, a_node );

		return is_the_cluster || is_the_cluster_desc;
	}
	
	
	private String find_displayed_ancestor_label( Node a_node){
		if ( a_node.is_displayed() ){
			return a_node.get_label();
		}else{
			return find_displayed_ancestor_label( a_node.get_parent() );
		}
	}
	
	//@return the edges under a same cluster
	public ArrayList find_external_cluster_edges( Node a_cluster ){			
		ArrayList	 cluster_edges	= new ArrayList();

		if ( a_cluster.is_leaf() ){
			return cluster_edges;
		}

		Tree	tree	= find_tree();
		ArrayList	 children	 = a_cluster.get_children();

		ArrayList edges			=	find_edges();
		for ( Iterator _i = edges.iterator() ; _i.hasNext(); ){
			String[] e = (String[])_i.next();
			
			String
				cluster_label		= a_cluster.get_label(),
				start_node_label	= e[0],
				end_node_label	= e[1];

			Node
				start_node	= search( start_node_label ),
				end_node	=search( end_node_label );
			
			boolean 
				is_from_the_cluster	= is_under_cluster( start_node, a_cluster ) && ! is_under_cluster( end_node, a_cluster ),
				is_to_the_cluster		= !is_under_cluster( start_node, a_cluster ) && is_under_cluster( end_node, a_cluster );
			
			
			if ( is_from_the_cluster || is_to_the_cluster){					
				//Debug.println( " A external cluster edge found: " + start_node_label + "-" + end_node_label, 3 );
				String 
					displayed_start_node_label	 = find_displayed_ancestor_label( start_node ),
					displayed_end_node_label	 = find_displayed_ancestor_label( end_node );

				Edge cluster_edge	= new Edge( search(displayed_start_node_label), search(displayed_end_node_label) );
			
				cluster_edges.add( cluster_edge  );
			}
		}
		
		return cluster_edges;
	}
	
	//@return the edges that connect a child to the highest degree child if there is no edge between them
	public ArrayList find_internal_cluster_psuedo_edges( Node cluster ){
		ArrayList cluster_psuedo_edges		= new ArrayList();

		if ( cluster.is_leaf() ){
			return cluster_psuedo_edges; 
		}

		String		highest_degree_child_label	= find_highest_degree_child_label( cluster );
		Node		highest_degree_child			= search( highest_degree_child_label );
		
		ArrayList	 children	 = cluster.get_children();
		for (  Iterator _i = children.iterator(); _i.hasNext(); ){
			Node child	= (Node)_i.next();

			if (!is_connected(child, highest_degree_child ) ){
				cluster_psuedo_edges.add( new Edge( child, highest_degree_child ) );
			}
		}

		return cluster_psuedo_edges;
	}
	

	public String find_highest_degree_child_label( Node a_cluster ){		
		String highest_child_degree_node_label = "";

		ArrayList children	= a_cluster.get_children();		
		
		int max_inside_cluster_degree = -1;

		for ( Iterator _i = children.iterator(); _i.hasNext(); ){
			Node child	= (Node)_i.next();
			int node_inside_cluster_degree = inside_cluster_degree( child );

			//Debug.println( "current max_inside_cluster_degree is: " + max_inside_cluster_degree, 3 );			
			//Debug.println( child.get_label() + " inside cluster degree is: " + node_inside_cluster_degree, 3 );

			if ( node_inside_cluster_degree > max_inside_cluster_degree ){
				max_inside_cluster_degree = node_inside_cluster_degree;
				highest_child_degree_node_label = child.get_label();
			}

			//Debug.println( "new max_inside_cluster_degree is: " + max_inside_cluster_degree, 3 );	
		}
		
		return highest_child_degree_node_label;
	}
	
	/**
		@return true if two clusters or their descendants have edge connected each other.
	*/
	public boolean is_connected( Node cluster, Node another_cluster){
		Tree	tree	= find_tree();

		ArrayList
			edges	 = find_edges();

		String
			cluster_label	= cluster.get_label(),
			another_cluster_label	= another_cluster.get_label();
				
		for ( Iterator _i = edges.iterator(); _i.hasNext(); ){
			String[] edge	= (String[])_i.next();

			String
				start_node_label	= edge[0],
				end_node_label	= edge[1];

			Node
				start_node	= search( start_node_label ),
				end_node	= search( end_node_label );
			
			//start_node is descedant of cluster or is the cluster itself
			if ( tree.is_ancestor( cluster, start_node ) || start_node_label.equals( cluster_label ) ){				
				if (  another_cluster_label.equals( end_node_label ) ){	//another_cluster is the end_node	
					return true;
				}else if ( tree.is_ancestor( another_cluster, end_node ) ){	//another_cluster is the ancestor of end_node
					return true;
				}
			}//end if tree.is_ancester( cluster, start_node )

			//end_node is descedant of cluster or is the cluster itself
			if ( tree.is_ancestor( cluster, end_node ) || end_node_label.equals( cluster_label ) ){
				if ( another_cluster_label.equals( start_node_label ) ){	//another _cluster is the start_node
					return true;
				}else if ( tree.is_ancestor( another_cluster, start_node ) ){
					return true;
				}
			}//end if tree.is_ancestor( cluster, end_Node )

		}//end of for Iterator

		return false;
	}

	//@return adjcant siblings. there  is an edge between cluster to the siblings.
	public ArrayList	find_adjcant_clusters( Node cluster ){
		ArrayList	 adjcant_clusters	= new ArrayList();
		
		if ( cluster.is_root() ){
			return adjcant_clusters;
		}		
		
		if ( cluster.is_leaf() ){
			return find_adjcant_siblings_of_a_leaf( cluster );
		}

		ArrayList	 siblings			= cluster.get_parent().get_children(); //all sbiling including the cluster itself.		
		Tree	tree	= find_tree();
		ArrayList	 descedants	= tree.find_descedants( cluster );

		for ( Iterator _i = descedants.iterator(); _i.hasNext(); ){
			Node	desc	= (Node)_i.next();

			if ( desc.is_leaf() ){
				ArrayList leaf_desc_adjcant_nodes	= find_adjcant_nodes_for_a_leaf_node( desc );

				for ( Iterator _j = leaf_desc_adjcant_nodes.iterator(); _j.hasNext(); ){
					Node adjcant_node	= (Node)_j.next();
					for ( Iterator _k = siblings.iterator(); _k.hasNext(); ){
						Node sibling	 = (Node)_k.next();
						
						if ( !sibling.get_label().equals( cluster.get_label() ) ){ // the sibling not the cluster itself
							if ( tree.is_ancestor( sibling, adjcant_node ) ){
								if ( !adjcant_clusters.contains(sibling ) ){
									adjcant_clusters.add( sibling );
								}//end of if !adjcant_clusters.contains( sibling );
								
							}//end of if tree.is_ancestor

						}//end of if !sibling.get_label()

					}//end of for _k
						

				}//end of for _j

			}//end of if desc.is_leaf
		}//end of for _i

		return adjcant_clusters;
	}
	
	//@this implement returns internal cluster degree
	public int degree( Node node ){
		ArrayList adjcant_nodes = find_adjcant_clusters( node );

		return adjcant_nodes.size();
	}

	public int inside_cluster_degree( Node node ){
		ArrayList adjcant_nodes = find_adjcant_clusters( node );
		int inside_cluster_degree = 0;

		for ( Iterator _i = adjcant_nodes.iterator(); _i.hasNext(); ){
			Node adjcant_node = (Node)_i.next();

			if ( adjcant_node.is_sibling( node ) ){
				inside_cluster_degree++;
			}
		}
		
		return inside_cluster_degree;
	}
	/**
		the label of nodes in the same level
	*/
	public ArrayList find_same_height_nodes( int height ){
		ArrayList all_same_height_nodes	= new ArrayList();
		
		Tree	tree	= find_tree();

		for ( Iterator _i = tree.get_tree().iterator(); _i.hasNext(); ){
			Node n	=(Node)_i.next();
			if ( tree.depth(n) == height ){
				all_same_height_nodes.add( n.get_label() );
			}
		}

		return all_same_height_nodes;	
	}

	public ArrayList find_same_height_non_psuedo_nodes( int height ){
		ArrayList all_same_height_nodes	= new ArrayList();
		
		Tree	tree	= find_tree();

		for ( Iterator _i = tree.get_tree().iterator(); _i.hasNext(); ){
			Node n	=(Node)_i.next();
			if ( n.get_is_psuedo() ){
				continue;
			}

			if ( tree.depth(n) == height ){
				all_same_height_nodes.add( n.get_label() );
			}
		}

		return all_same_height_nodes;	
	}
	/**
		the label of nodes in the same level
	*/
	protected ArrayList find_displayed_same_height_nodes( int height ){
		ArrayList all_same_height_nodes	= new ArrayList();
		
		Tree	tree	= find_tree();

		for ( Iterator _i = tree.get_tree().iterator(); _i.hasNext(); ){
			Node n	=(Node)_i.next();
			if ( tree.depth(n) == height && n.is_displayed() ){
				all_same_height_nodes.add( n.get_label() );
			}
		}

		return all_same_height_nodes;	
	}

	//==================================================
	// package utils
	//==================================================
	protected Node search( Collection nodes, String label ){
		Node search_result	= new Node();
	
		for ( Iterator iter = nodes.iterator() ; iter.hasNext() ; ){
			Node tn	= (Node) iter.next();
			if ( tn.has_label( label ) ){
				search_result =  tn;
				break;
			}
		}
		
		return search_result;
	}

	//==================================================
	// class utils
	//==================================================
	//@param node : a leaf node.
	private ArrayList	find_adjcant_nodes_for_a_leaf_node( Node node ){
		ArrayList	 adjcant_nodes	= new ArrayList();
		ArrayList edges				=	find_edges();
		
		for ( Iterator _i = edges.iterator() ; _i.hasNext(); ){
			String[] e = (String[])_i.next();
			
			String
				node_label			= node.get_label(),
				start_node_label	= e[0],
				end_node_label	= e[1];

			Node
				start_node	= search( start_node_label ),
				end_node	=search( end_node_label );

			if ( node_label.equals( start_node_label ) ){
				adjcant_nodes.add( end_node );
			}else if ( node_label.equals( end_node_label )  ){// node is  end node
				adjcant_nodes.add( start_node );
			}//end of if-else			
		}//end of for

		return adjcant_nodes;
	}
	
	private ArrayList find_adjcant_siblings_of_a_leaf( Node node ){
		if ( node.is_root() ){
			return null;
		}

		ArrayList all_adjcant_nodes	= find_adjcant_nodes_for_a_leaf_node( node );

		ArrayList adjcant_nodes_in_same_cluster = new ArrayList();

		for ( Iterator _i = all_adjcant_nodes.iterator(); _i.hasNext(); ){
			Node	an_adjcant_node	= (Node)_i.next();
			if ( node.is_sibling( an_adjcant_node ) ){
				adjcant_nodes_in_same_cluster.add( an_adjcant_node );
			}
		}

		return adjcant_nodes_in_same_cluster;
	}
}
